﻿using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;

namespace Stimik
{  
    class RubikSolver
    {    
        private Node start;//node pertama, satu2nya node yang tidak punya parent                  
        private List<int> path;
        int soldepth;

        public List<int> getSolPath
        {
            get { return path; }
        }

        public Rubiks getStartRubiks
        {
            get { return start.r; }
        }

        public RubikSolver(string filename)
        {
            //load rubiks dari file eksternal dan bikin node start
            path = new List<int>();
            readFile(filename);            
        }

        public bool solve()
        {
            path.Clear();
            soldepth = 14;
            long idx = 0;
            bool done = false;
            Stack<Node> qnode = new Stack<Node>();//node to be visited
            List<Node> vnode = new List<Node>();//visited node                            
            qnode.Push(start);
            while(qnode.Count>0) {
                ++idx;
                //System.Diagnostics.Debug.WriteLine("i : " + (idx));
                Node node = qnode.Pop();
                vnode.Add(node);
                //printNode(node);
                if (node.r.isSolved())
                {
                    soldepth = node.depth;
                    done = true;       
                    makePath(node);                    
                    System.Diagnostics.Debug.WriteLine("KETEMU!!!");
                    //return;
                }
                else
                {
                    if(bound(node)) {                        
                        expandNode(node, qnode,vnode);
                    }
                }
            }            
            if(done) {
                System.Diagnostics.Debug.Write("Solusi ketemu(" + idx + " perhitungan) : ");
                for (int i = 0; i < path.Count; i++)
                {
                    System.Diagnostics.Debug.Write(path[i] + " ");
                }
                System.Diagnostics.Debug.WriteLine("");
                return true;
            }else{
                System.Diagnostics.Debug.WriteLine("Solusi tidak ketemu");
                return false;
            }            
        }

        private void makePath(Node node)
        {
            Node parnode = node;
            List<int> newpath = new List<int>();            
            while(parnode!=null) {
                newpath.Insert(0, parnode.typeop);
                parnode = parnode.parent;
            }
            for (int i = 0; i < newpath.Count; i++)
            {
                System.Diagnostics.Debug.Write(newpath[i] + " ");
            }
            if(path.Count==0 || newpath.Count<path.Count) {
                path = newpath;
            }
            System.Diagnostics.Debug.WriteLine("");
        }

        private void printNode(Node node)
        {
            System.Diagnostics.Debug.WriteLine("Depth : " + node.depth);
            string str;
            if(node.typeop==1) 
            {
                str = "RIGHTC";
            }else if(node.typeop==2) 
            {
                str = "RIGHTCC";
            }else if (node.typeop == 3)
            {
                str = "UPC";
            }else if (node.typeop == 4)
            {
                str = "UPCC";
            }else if (node.typeop == 5)
            {
                str = "FACEC";
            }
            else if (node.typeop == 6)
            {
                str = "FACECC";
            }
            else
            {
                str = "NONE";
            }
            System.Diagnostics.Debug.WriteLine("Operasi : " + str);
            node.r.testprint();
            System.Diagnostics.Debug.WriteLine("");
        }

        private void expandNode(Node node, Stack<Node> qnode,List<Node> vnode) {
            Node rightc = new Node(node.r.getTurnRight(), node, Rubiks.RIGHTC);
            Node rightcc = new Node(node.r.getTurnRight(true), node,Rubiks.RIGHTCC);
            Node upc = new Node(node.r.getTurnUp(), node, Rubiks.UPC);
            Node upcc = new Node(node.r.getTurnUp(true), node, Rubiks.UPCC);          
            Node facec = new Node(node.r.getTurnFace(), node, Rubiks.FACEC);
            Node facecc = new Node(node.r.getTurnFace(true), node, Rubiks.FACECC);                                
            if((node.typeop!=Rubiks.RIGHTC || node.parent.typeop!=Rubiks.RIGHTC) && !checkHasVisited(rightc,vnode)) 
            {                
                //System.Diagnostics.Debug.WriteLine("rightc");
                qnode.Push(rightc);
            }
            if ((node.typeop != Rubiks.RIGHTCC || node.parent.typeop != Rubiks.RIGHTCC) && !checkHasVisited(rightcc, vnode))
            {                
                //System.Diagnostics.Debug.WriteLine("rightcc");
                qnode.Push(rightcc);
            }
            if ((node.typeop != Rubiks.UPC || node.parent.typeop != Rubiks.UPC) && !checkHasVisited(upc, vnode))
            {                
                //System.Diagnostics.Debug.WriteLine("upc");
                qnode.Push(upc);
            }
            if ((node.typeop != Rubiks.UPCC || node.parent.typeop != Rubiks.UPCC) && !checkHasVisited(upcc, vnode))
            {                
                //System.Diagnostics.Debug.WriteLine("upcc");
                qnode.Push(upcc);
            }
            if ((node.typeop != Rubiks.FACEC || node.parent.typeop != Rubiks.FACEC) && !checkHasVisited(facec, vnode))
            {                
                //System.Diagnostics.Debug.WriteLine("facec");
                qnode.Push(facec);
            }
            if ((node.typeop != Rubiks.FACECC || node.parent.typeop != Rubiks.FACECC) && !checkHasVisited(facecc, vnode))
            {                
                //System.Diagnostics.Debug.WriteLine("facecc belum ada!");
                qnode.Push(facecc);
            }            
        }

        private bool bound(Node node)
        {
            if(node.depth<soldepth) {
                return true;
            }
            return false;
        }

        private bool checkHasVisited(Node n, List<Node> vnode)
        {            
            //TODO : gak pake check
            return false;
            for(int i=0;i<vnode.Count;i++) {
                if(n.r.isEqualz(vnode[i].r)) {                    
                    //n.r.testprint();
                    //vnode[i].r.testprint();
                    return true;
                }
            }
            return false;
        }

        //baca file eksternal dan menaruh format rubiks yang dibaca di dalam node start
        private void readFile(string filename)
        {
            StreamReader MyStreamReader = new StreamReader(filename);
            char[ , , ] colourPos = new char[7, 2, 2];
            int ch;
            int index1 = 1;
            int index2 = 0;
            int index3 = 0;
            int size = 2;

            while ((ch = MyStreamReader.Read()) != -1)
            {
                char colour = Convert.ToChar(ch);                

                if ((colour.Equals('1')) || (colour.Equals('2')) || (colour.Equals('3')) || (colour.Equals('4')) || (colour.Equals('5')) || (colour.Equals('6')))
                {
                    colourPos[index1, index2, index3] = colour;
                    index3++;
                }

                if (index3 == 2)
                {
                    index2++;
                    index3 = 0;
                }

                if (index2 == 2)
                {
                    index1++;
                    index2 = 0;
                }
            }
            Rubiks r = new Rubiks(size,
                                 new char[,] { { colourPos[1, 0, 0], colourPos[1, 0, 1] }, { colourPos[1, 1, 0], colourPos[1, 1, 1] } },
                                 new char[,] { { colourPos[2, 0, 0], colourPos[2, 0, 1] }, { colourPos[2, 1, 0], colourPos[2, 1, 1] } },
                                 new char[,] { { colourPos[3, 0, 0], colourPos[3, 0, 1] }, { colourPos[3, 1, 0], colourPos[3, 1, 1] } },
                                 new char[,] { { colourPos[4, 0, 0], colourPos[4, 0, 1] }, { colourPos[4, 1, 0], colourPos[4, 1, 1] } },
                                 new char[,] { { colourPos[5, 0, 0], colourPos[5, 0, 1] }, { colourPos[5, 1, 0], colourPos[5, 1, 1] } },
                                 new char[,] { { colourPos[6, 0, 0], colourPos[6, 0, 1] }, { colourPos[6, 1, 0], colourPos[6, 1, 1] } });
            start = new Node(r,null);            
            path.Clear();
            MyStreamReader.Close();
        }

        class Node
        {
            public Rubiks r;//state rubiks di node tersebut                       
            public Node parent;//parent node ini (jika root, maka parent bernilai null)
            public int depth=0;//depth node ini di tree
            public int typeop=0;            

            public Node(Rubiks r, Node parent, int typeop=0)
            {
                this.parent = parent;
                this.r = r;
                if (parent != null)
                {
                    this.depth = parent.depth + 1;
                    this.typeop = typeop;
                }                
            }
        }
    }
}
